Public key encryption systems have been proposed for encrypting information for security and authentication purposes. The most widely known and accepted public key encryption system, known as RSA after its inventors Rivest, Shamir, and Adleman, operates in accordance with an algorithm which is described in Rivest et al. U.S. Pat. No. 4,405,829 issued Sep. 30, 1983 and entitled "Cryptographic Communications System and Method".
Briefly described, RSA uses two randomly chosen large prime numbers p and q, and determines their product n. A large number d is chosen so that d and the product (p-1)*(q-1) have no common factor greater than one. A number e is determined such that (e*d) modulo ((p-1)*(q-1))=1. The notation "x modulo y" means the remainder of dividing x by y using integer division. The pairs of numbers (e, n) and (d, n) constitute a public key and a private key respectively. The security of the algorithm resides in the fact that the numbers p and q are very large (e.g. 100 decimal digits or more) so that n is extremely large, and there is no known efficient algorithm for factoring such extremely large numbers.
To encrypt using RSA, information is broken into blocks each of which can be represented as an integer from 1 to n-1. Each such integer T is raised to the power e, modulo n, to produce an encrypted number C. This is decrypted by raising it to the power d, modulo n. Thus C=T.sup.e modulo n, and T=C.sup.a modulo n. The calculations represented by these equations can be performed by a process referred to as modular exponentiation, which is the process of raising a first large positive integer to the power of a second large positive integer, and determining the result modulo a third large positive integer.
A problem with modular exponentiation is that it can be unacceptably slow, even when using very fast processing devices. For effective use of RSA, modular exponentiation of binary numbers of about 256 bits is typically required (a 512-bit RSA decryption can be effected using two 256-bit modular exponentiations). Such large numbers must each be treated in practical processors as multiple words, for example as 12 words each of 24 bits as described further below. The words of each number must be handled sequentially, so that processing of the numbers can involve a large number of sequential steps, and hence a considerable amount of time.
For example, the modular exponentiation process involves many multiplications of large numbers. To multiply one 12-word number as described above by another 12-word number involves 12.sup.2 =144 multiplications of two 24-bit words, as well as numerous adding or accumulation steps and manipulation of the partial results which are produced by the multiplication and accumulation steps.
The speed with which such a multiplication of large numbers can be performed, and hence the speeds of the modular exponentiation process and the RSA encryption or decryption process, is thus dependent upon three factors, namely the speed of the processor, the size(s) of words which the processor can multiply and accumulate, and the speed with which the partial results are manipulated. The first two of these factors are determined by hardware constraints, and maximum speeds are effectively predetermined for a given processor. The third of these factors has been found to have a major impact on the overall multiplication speed, and is addressed by the present invention.
An object of this invention, therefore, is to provide an improved method of multiplying large numbers in a processor.